package two;

public class A029 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //1.如何定位到倒数第N个节点 -- 先找N步然后两个指针一起找
        //2.删除节点 (1)删除头结点（2）其他节点
        ListNode fast = head;
        for(int i=0;i<n;i++) {
            fast = fast.next;
        }
        ListNode cur = head;
        ListNode prev = head;
        int flag=1;
        while(fast!=null) {
            cur = cur.next;
            fast = fast.next;
            if(flag==1) {
                prev=head;
                flag++;
            }else {
                prev = prev.next;
            }
        }
        //
        if(cur==head) {
            head = head.next;
        }else {
            prev.next = cur.next;
            cur.next = null;
        }
        return head;
    }
}
